unit heContnrs_BTreeSet_test;

{$mode objfpc}{$H+}

interface

uses
  fpcunit,
  heContnrs,
  heContnrs_test;

type

  BTreeSetInt = type Integer;
  BTreeSetStr = type String;

  TTestBTreeSetInt = specialize TheBTreeSet<BTreeSetInt>;
  TTestBTreeSetStr = specialize TheBTreeSet<BTreeSetStr>;

  { TTestCmpBTreeSetInt }

  _TTestCmpBTreeSetInt = specialize TheCmpBTreeSet<Integer>;
  TTestCmpBTreeSetInt = class(_TTestCmpBTreeSetInt)
  public
    function Compare(const A, B: Integer): Integer; override;
  end;

  { TTestCmpBTreeSetStr }

  _TTestCmpBTreeSetStr = specialize TheCmpBTreeSet<String>;
  TTestCmpBTreeSetStr = class(_TTestCmpBTreeSetStr)
  public
    function Compare(const A, B: String): Integer; override;
  end;

  { TTestCmpBTreeSetInterface }

  _TTestCmpBTreeSetInterface = specialize TheCmpBTreeSet<IInterface>;
  TTestCmpBTreeSetInterface = class(_TTestCmpBTreeSetInterface)
  public
    function Compare(const A, B: IInterface): Integer; override;
  end;

  { TTestBTreeSetObj }

  _TTestBTreeSetObj = specialize TheObjectBTreeSet<TTracedObject>;
  TTestBTreeSetObj = class(_TTestBTreeSetObj)
  public
    constructor Create(const AOwnObjects: Boolean = True);
    function Compare(const A, B: TTracedObject): Integer; override;
  end;

  { TheBTreeSetTest }

  generic TheBTreeSetTest<TBTreeSet, TItem> = class(TTestCase)
  private
    Tree: TBTreeSet;
  protected
    function Item(const N: Integer): TItem; virtual; // abstract
    function Value(const It: TItem): Integer; virtual; // abstract;
    procedure Done(var It: TItem); virtual;
    procedure SetUp; override;
    procedure TearDown; override;
  published
    procedure TestCreate;
    procedure TestInclude;
    procedure TestExclude;
    procedure TestClear;
    procedure TestFirst;
    procedure TestLast;
    procedure TestMembership;
  end;

  { TheIntBTreeSetTest }

  _TheIntBTreeSetTest = specialize TheBTreeSetTest<TTestBTreeSetInt, Integer>;
  TheIntBTreeSetTest = class(_TheIntBTreeSetTest)
  protected
    function Item(const N: Integer): Integer; override;
    function Value(const It: Integer): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
    procedure TestGetRange;
  end;

  { TheStrBTreeSetTest }

  _TheStrBTreeSetTest = specialize TheBTreeSetTest<TTestBTreeSetStr, String>;
  TheStrBTreeSetTest = class(_TheStrBTreeSetTest)
  protected
    function Item(const N: Integer): String; override;
    function Value(const It: String): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
    procedure TestGetRange;
  end;

  { TheIntCmpBTreeSetTest }

  _TheIntCmpBTreeSetTest = specialize TheBTreeSetTest<TTestCmpBTreeSetInt, Integer>;
  TheIntCmpBTreeSetTest = class(_TheIntCmpBTreeSetTest)
  protected
    function Item(const N: Integer): Integer; override;
    function Value(const It: Integer): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
    procedure TestGetRange;
  end;

  { TheStrCmpBTreeSetTest }

  _TheStrCmpBTreeSetTest = specialize TheBTreeSetTest<TTestCmpBTreeSetStr, String>;
  TheStrCmpBTreeSetTest = class(_TheStrCmpBTreeSetTest)
  protected
    function Item(const N: Integer): String; override;
    function Value(const It: String): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
    procedure TestGetRange;
  end;

  { TheInterfaceCmpBTreeSetTest }

  _TheInterfaceCmpBTreeSetTest = specialize TheBTreeSetTest<TTestCmpBTreeSetInterface, IInterface>;
  TheInterfaceCmpBTreeSetTest = class(_TheInterfaceCmpBTreeSetTest)
  protected
    function Item(const N: Integer): IInterface; override;
    function Value(const It: IInterface): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
    procedure TestGetRange;
  end;

  { TheObjectBTreeSetTest }

  _TheObjectBTreeSetTest = specialize TheBTreeSetTest<TTestBTreeSetObj, TTracedObject>;
  TheObjectBTreeSetTest = class(_TheObjectBTreeSetTest)
  protected
    function Item(const N: Integer): TTracedObject; override;
    function Value(const It: TTracedObject): Integer; override;
    procedure Done(var It: TTracedObject); override;
  published
    procedure TestCreate2;
    procedure TestCreate3;
    procedure TestGetEnumerator;
    procedure TestReversed;
    procedure TestGetRange;
  end;

implementation

uses
  Classes,
  SysUtils,
  testregistry;

function I2S(N: Integer): String;
var
  R: LongRec absolute N;
  I: Integer;
begin
  SetLength(Result, Succ(High(R.Bytes)));
  R.Bytes[High(R.Bytes)] := R.Bytes[High(R.Bytes)] xor $80;
  for I := 0 to High(R.Bytes) do
    PByte(Result)[I] := R.Bytes[High(R.Bytes) - I];
end;

function S2I(const S: String): Integer;
var
  R: LongRec absolute Result;
  I: Integer;
begin
  for I := 0 to High(R.Bytes) do
    R.Bytes[High(R.Bytes) - I] := PByte(S)[I];
  R.Bytes[High(R.Bytes)] := R.Bytes[High(R.Bytes)] xor $80;
end;

{ TTestCmpBTreeSetInt }

function TTestCmpBTreeSetInt.Compare(const A, B: Integer): Integer;
begin
  Result := A - B;
end;

{ TTestCmpBTreeSetStr }

function TTestCmpBTreeSetStr.Compare(const A, B: String): Integer;
begin
  Result := CompareStr(A, B);
end;

{ TTestCmpBTreeSetInterface }

function TTestCmpBTreeSetInterface.Compare(const A, B: IInterface): Integer;
begin
  Result := (A as TInterfacedTracedObject).ID - (B as TInterfacedTracedObject).ID;
end;

{ TTestBTreeSetObj }

constructor TTestBTreeSetObj.Create(const AOwnObjects: Boolean);
begin
  inherited Create(AOwnObjects);
end;

function TTestBTreeSetObj.Compare(const A, B: TTracedObject): Integer;
begin
  Result := A.ID - B.ID;
end;

{ TheIntBTreeSetTest }

function TheIntBTreeSetTest.Item(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntBTreeSetTest.Value(const It: Integer): Integer;
begin
  Result := It;
end;

procedure TheIntBTreeSetTest.TestGetEnumerator;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) < Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntBTreeSetTest.TestReversed;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree.Reversed do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree.Reversed do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) > Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntBTreeSetTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TItem;
  begin
    I := 0;
    for V in Tree.Range[Item(RangeFrom), Item(RangeTo)] do begin
      AssertEquals(Expect[I], Value(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheIntBTreeSetTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Tree.Include(Item(10));
      Tree.Include(Item(20));
      Tree.Include(Item(25));
      Tree.Include(Item(30));
      if B then
        Tree.Include(Item(40));

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

{ TheStrBTreeSetTest }

function TheStrBTreeSetTest.Item(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheStrBTreeSetTest.Value(const It: String): Integer;
begin
  Result := S2I(It);
end;

procedure TheStrBTreeSetTest.TestGetEnumerator;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) < Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrBTreeSetTest.TestReversed;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree.Reversed do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree.Reversed do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) > Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrBTreeSetTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TItem;
  begin
    I := 0;
    for V in Tree.Range[Item(RangeFrom), Item(RangeTo)] do begin
      AssertEquals(Expect[I], Value(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheStrBTreeSetTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Tree.Include(Item(10));
      Tree.Include(Item(20));
      Tree.Include(Item(25));
      Tree.Include(Item(30));
      if B then
        Tree.Include(Item(40));

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

{ TheIntCmpBTreeSetTest }

function TheIntCmpBTreeSetTest.Item(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntCmpBTreeSetTest.Value(const It: Integer): Integer;
begin
  Result := It;
end;

procedure TheIntCmpBTreeSetTest.TestGetEnumerator;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) < Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntCmpBTreeSetTest.TestReversed;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree.Reversed do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree.Reversed do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) > Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntCmpBTreeSetTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TItem;
  begin
    I := 0;
    for V in Tree.Range[Item(RangeFrom), Item(RangeTo)] do begin
      AssertEquals(Expect[I], Value(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheIntCmpBTreeSetTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Tree.Include(Item(10));
      Tree.Include(Item(20));
      Tree.Include(Item(25));
      Tree.Include(Item(30));
      if B then
        Tree.Include(Item(40));

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

{ TheStrCmpBTreeSetTest }

function TheStrCmpBTreeSetTest.Item(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheStrCmpBTreeSetTest.Value(const It: String): Integer;
begin
  Result := S2I(It);
end;

procedure TheStrCmpBTreeSetTest.TestGetEnumerator;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) < Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrCmpBTreeSetTest.TestReversed;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree.Reversed do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree.Reversed do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) > Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrCmpBTreeSetTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TItem;
  begin
    I := 0;
    for V in Tree.Range[Item(RangeFrom), Item(RangeTo)] do begin
      AssertEquals(Expect[I], Value(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheStrCmpBTreeSetTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Tree.Include(Item(10));
      Tree.Include(Item(20));
      Tree.Include(Item(25));
      Tree.Include(Item(30));
      if B then
        Tree.Include(Item(40));

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

{ TheInterfaceCmpBTreeSetTest }

function TheInterfaceCmpBTreeSetTest.Item(const N: Integer): IInterface;
begin
  Result := TInterfacedTracedObject.Create(nil, N);
end;

function TheInterfaceCmpBTreeSetTest.Value(const It: IInterface): Integer;
begin
  Result := (It as TInterfacedTracedObject).ID;
end;

procedure TheInterfaceCmpBTreeSetTest.TestGetEnumerator;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) < Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheInterfaceCmpBTreeSetTest.TestReversed;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree.Reversed do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree.Reversed do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) > Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheInterfaceCmpBTreeSetTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TItem;
  begin
    I := 0;
    for V in Tree.Range[Item(RangeFrom), Item(RangeTo)] do begin
      AssertEquals(Expect[I], Value(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheInterfaceCmpBTreeSetTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Tree.Include(Item(10));
      Tree.Include(Item(20));
      Tree.Include(Item(25));
      Tree.Include(Item(30));
      if B then
        Tree.Include(Item(40));

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

{ TheObjectBTreeSetTest }

function TheObjectBTreeSetTest.Item(const N: Integer): TTracedObject;
begin
  if N = -1 then
    Exit(nil);
  Result := TTracedObject.Create(nil, N);
end;

function TheObjectBTreeSetTest.Value(const It: TTracedObject): Integer;
begin
  if It = nil then
    Exit(-1);
  Result := It.ID;
end;

procedure TheObjectBTreeSetTest.Done(var It: TTracedObject);
begin
  FreeAndNil(It);
end;

procedure TheObjectBTreeSetTest.TestCreate2;
var
  Tracer: TBits;
  L: TTestBTreeSetObj;
begin
  L := TTestBTreeSetObj.Create(True);
  try
    AssertTrue(L.OwnObjects);
    Tracer := TBits.Create;
    try
      L.Include(TTracedObject.Create(Tracer, 1));
      L.Clear;
      AssertFalse('Item dead', Tracer[1]);
    finally
      Tracer.Free;
    end;
  finally
    L.Free;
  end;
end;

procedure TheObjectBTreeSetTest.TestCreate3;
var
  Tracer: TBits;
  L: TTestBTreeSetObj;
  Obj: TTracedObject;
begin
  L := TTestBTreeSetObj.Create(False);
  try
    AssertFalse(L.OwnObjects);
    Tracer := TBits.Create;
    try
      Obj := TTracedObject.Create(Tracer, 1);
      try
        L.Include(Obj);
        L.Clear;
        AssertTrue('Item alive', Tracer[1]);
      finally
        Obj.Free;
      end;
    finally
      Tracer.Free;
    end;
  finally
    L.Free;
  end;
end;

procedure TheObjectBTreeSetTest.TestGetEnumerator;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) < Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheObjectBTreeSetTest.TestReversed;
const N = 513;
var
  I, J: Integer;
  L, V: TItem;
begin
  J := 0;
  for V in Tree.Reversed do
    Inc(J);
  AssertEquals('J0', 0, J);
  for I := 0 to N - 1 do begin
    AssertEquals('.Count', I, Tree.Count);
    AssertFalse('.Include', Tree.Include(Item(I)));
    J := 0;
    L := Item(-1);
    for V in Tree.Reversed do begin
      AssertTrue('V', (Value(V) >= 0) and (Value(V) <= I));
      if Value(L) >= 0 then
        AssertTrue('Ordering', Value(L) > Value(V));
      L := V;
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheObjectBTreeSetTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    RF, RT, V: TItem;
  begin
    I := 0;
    RF := Item(RangeFrom);
    RT := Item(RangeTo);
    try
      for V in Tree.Range[RF, RT] do begin
        AssertEquals(Expect[I], Value(V));
        Inc(I);
      end;
      AssertEquals(Length(Expect), I);
    finally
      Done(RT);
      Done(RF);
    end;
  end;

// procedure TheObjectBTreeSetTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Tree.Include(Item(10));
      Tree.Include(Item(20));
      Tree.Include(Item(25));
      Tree.Include(Item(30));
      if B then
        Tree.Include(Item(40));

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

{ TheBTreeSetTest }

function TheBTreeSetTest.Item(const N: Integer): TItem;
begin
  Assert(N = N); // hint off
  Initialize(Result); // hint off
  raise EAbstractError.Create(Format('%s.Item', [ClassName]));
end;

function TheBTreeSetTest.Value(const It: TItem): Integer;
begin
  Assert(@It = @It); // hint off
  Initialize(Result); // hint off
  raise EAbstractError.Create(Format('%s.Value', [ClassName]));
end;

procedure TheBTreeSetTest.Done(var It: TItem);
begin
  Assert(@It = @It); // hint off
end;

procedure TheBTreeSetTest.SetUp;
begin
  Tree := TBTreeSet.Create;
end;

procedure TheBTreeSetTest.TearDown;
begin
  FreeAndNil(Tree);
end;

procedure TheBTreeSetTest.TestCreate;
begin
  AssertEquals(0, Tree.Count);
end;

procedure TheBTreeSetTest.TestInclude;
var Item0, Item10: TItem;
begin
  AssertEquals('a1) .Count', 0, Tree.Count);
  AssertFalse('b1) .Include', Tree.Include(Item(0)));
  AssertEquals('c1) .Count', 1, Tree.Count);
  Item0 := Item(0);
  try
    AssertTrue('d1) .Include', Tree.Include(Item0));
    AssertEquals('e1) .Count', 1, Tree.Count);
  finally
    Done(Item0);
  end;
  TearDown;

  SetUp;
  AssertEquals('a2) .Count', 0, Tree.Count);
  AssertFalse('b2) .Include', Tree.Include(Item(0)));
  AssertEquals('c2) .Count', 1, Tree.Count);
  AssertFalse('d2) .Include', Tree.Include(Item(10)));
  AssertEquals('e2) .Count', 2, Tree.Count);
  Item0 := Item(0);
  Item10 := Item(10);
  try
    AssertTrue('f2) .Include', Tree.Include(Item0));
    AssertTrue('g2) .Include', Tree.Include(Item10));
  finally
    Done(Item0);
    Done(Item10);
  end;
  AssertEquals('h2) .Count', 2, Tree.Count);
  TearDown;

  SetUp;
  AssertEquals('a3) .Count', 0, Tree.Count);
  AssertFalse('b3) .Include', Tree.Include(Item(10)));
  AssertEquals('c3) .Count', 1, Tree.Count);
  AssertFalse('d3) .Include', Tree.Include(Item(0)));
  AssertEquals('e3( .Count', 2, Tree.Count);
  Item0 := Item(0);
  Item10 := Item(10);
  try
    AssertTrue('f3) .Include', Tree.Include(Item10));
    AssertTrue('g3) .Include', Tree.Include(Item0));
  finally
    Done(Item0);
    Done(Item10);
  end;
  AssertEquals('h3) .Count', 2, Tree.Count);
end;

procedure TheBTreeSetTest.TestExclude;
var Item0_, Item10_, Item0, Item10: TItem;
begin
  Item0_ := Item(0);
  Item0 := Item(0);
  try
    AssertFalse('a1) .Exclude', Tree.Exclude(Item0));
    AssertFalse('b1) .Include', Tree.Include(Item0_));
    AssertTrue('c1) .Exclude', Tree.Exclude(Item0));
    AssertFalse('d1) .Exclude', Tree.Exclude(Item0));
    AssertEquals('e1', 0, Tree.Count);
  finally
    Done(Item0_);
    Done(Item0);
  end;
  TearDown;

  SetUp;
  Item0_ := Item(0);
  Item0 := Item(0);
  Item10_ := Item(10);
  Item10 := Item(10);
  try
    AssertFalse('a2) .Exclude', Tree.Exclude(Item0));
    AssertFalse('b2) .Exclude', Tree.Exclude(Item10));
    AssertFalse('c2) .Include', Tree.Include(Item0));
    AssertTrue('d2) .Exclude', Tree.Exclude(Item0_));
    AssertFalse('e2) .Exclude', Tree.Exclude(Item0_));
    AssertFalse('f2) .Exclude', Tree.Exclude(Item10_));
    AssertEquals('g2', 0, Tree.Count);
  finally
    Done(Item0);
    Done(Item0_);
    Done(Item10);
    Done(Item10_);
  end;
  TearDown;

  SetUp;
  Item0_ := Item(0);
  Item0 := Item(0);
  Item10_ := Item(10);
  Item10 := Item(10);
  try
    AssertFalse('a3) .Exclude', Tree.Exclude(Item0));
    AssertFalse('b3) .Exclude', Tree.Exclude(Item10));
    AssertFalse('c3) .Include', Tree.Include(Item0));
    AssertFalse('d3) .Include', Tree.Include(Item10));
    AssertTrue('e3) .Include', Tree.Include(Item0_));
    AssertTrue('f3) .Exclude', Tree.Exclude(Item0_));
    AssertTrue('g3) .Exclude', Tree.Exclude(Item10_));
    AssertFalse('h3) .Exclude', Tree.Exclude(Item0_));
    AssertFalse('i3) .Exclude', Tree.Exclude(Item10_));
    AssertEquals('j3', 0, Tree.Count);
  finally
    Done(Item0);
    Done(Item0_);
    Done(Item10);
    Done(Item10_);
  end;
end;

procedure TheBTreeSetTest.TestClear;
const N = 10;
var I: Integer;
begin
  for I := 0 to N - 1 do
    Tree.Include(Item(I));
  Tree.Clear;
  AssertEquals('.Count', 0, Tree.Count);
end;

procedure TheBTreeSetTest.TestFirst;
var ItemA, ItemB: TItem;
begin
  ItemA := Item(100);
  Tree.Include(ItemA);
  AssertEquals('a1) .First', Value(ItemA), Value(Tree.First));
  ItemB := Item(200);
  Tree.Include(ItemB);
  AssertEquals('a2) .First', Value(ItemA), Value(Tree.First));
  Assert(@ItemB = @ItemB); // hint off
end;

procedure TheBTreeSetTest.TestLast;
var ItemA, ItemB: TItem;
begin
  ItemA := Item(100);
  Tree.Include(ItemA);
  AssertEquals('a1) .Last', Value(ItemA), Value(Tree.Last));
  ItemB := Item(200);
  Tree.Include(ItemB);
  AssertEquals('a2) .Last', Value(ItemB), Value(Tree.Last));
end;

procedure TheBTreeSetTest.TestMembership;
var
  I, Bit: Byte;
  A: array [0..4] of TItem;
begin
  for I := Low(A) to High(A) do
    A[I] := Item(I);
  for I := 0 to (2 shl High(A)) - 1 do begin
    for Bit := Low(A) to High(A) do
      Tree[A[Bit]] := (I and (1 shl Bit)) <> 0;
    for Bit := Low(A) to High(A) do
      AssertEquals((I and (1 shl Bit)) <> 0, Tree[A[Bit]]);
  end;
  Assert(@A = @A); // hint off
end;

initialization
  RegisterTests([
    TheIntBTreeSetTest,
    TheStrBTreeSetTest,
    TheIntCmpBTreeSetTest,
    TheStrCmpBTreeSetTest,
    TheInterfaceCmpBTreeSetTest,
    TheObjectBTreeSetTest
  ]);

end.

